package arrays;

import java.util.Arrays;

/**
 * 题目：求需要排序的最短子数组
 * y: [0,2,4,1,8]
 * 只需要排序 2 4 1就可以使用数组递增有序，所以返回3
 *
 * @Author Gavin
 * @date 2022.01.17 21:19
 */
public class array_16 {
    /**
     * 解题思路：
     * 第一种方法：先把数组排序，然后和元数组进行对比，左右下标进行对比，如果元数组
     * 下标对应的值和排序后下标对应的值相同就说明有序
     */
    //Time:O(N*log(n)) Space:O(n)
    public static int solution_1(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        int i = 0, j = nums.length - 1;
        while (i < nums.length && nums[i] == sorted[i]) ++i;
        while (j >= 0 && nums[j] == sorted[j]) --j;
        return Math.max(j - i + 1, 0);
    }

    /**
     * 第二种方法：
     * 我们要明确排序后数组的特点，从左往右是依次递增的
     * 所以我们可以使用两个指针分别从左往右和从右往左依次移动，左边移动到
     * i+1 < i 的时候暂停移动，右边j移动到j < j-1 的时候暂停移动，这样就找到了两个边界值以及一个
     * 区间 i ~ j ，然后从这个区间找到最大值和最小值，拿最小值和0到i进行比较，因为此时0到i是有序的，
     * 同理用最大值和j到数组末尾进行对比，这样就能找到最小的区间了，只需要遍历两次数组，时间复杂度为
     * o(n)
     */
    public static int solution_2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length-1;
        int i = 0, j = n;
        while (i < n && nums[i + 1] >= nums[i]) ++i;
        while (j > 0 && nums[j - 1] <= nums[j]) --j;
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        //求i~j之间的最大值和最小值
        for (int k = i; k <= j; ++k) {
            min = Math.min(min, nums[k]);
            max = Math.max(max, nums[k]);
        }
        while (i >= 0 && min < nums[i]) --i;//最后会多减一次
        while (j <= n && max > nums[j]) ++j;//最后会多加一次
        //i+1 ~ j-1  所以长度就为： j-1 - (i+1) +1
        return Math.max(j - i - 1, 0);//和0比较是因为如果是递增有序的数组那么j-i就是负数了
    }

    /**
     * 第三种方法：
     * 仍然是利用递增数组的特点，我们只需要遍历一次数组，同样我们使用两个指针进行移动
     * i从左到右移动，每移动一个就求最大值看是否和当前值相等（因为递增的特点），同理，j从末尾开始向左
     * 移动，并求最小值是否和当前值相等。
     * 最后求j-i+1的大小就行
     */
    public int solution_3(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int i = 0, j = -1, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int k = 0; k < n; k++) {
            max = Math.max(max, nums[k]);
            if (nums[k] != max) j = k;
            int p = n - 1 -k;
            min = Math.min(min, nums[p]);
            if (nums[p] != min) i = p;
        }
        return j - i + 1;
    }


}
